package listbyorder.access001_100.test43;

import java.util.ArrayList;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/5/31 16:10
 */
public class Solution1 {

    // 有问题————————思路是对的，代码太复杂，AC答案出错
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        List<String> midRes = helper(num1, num2);
        return getAns(midRes);
    }

    private String getAns(List<String> midRes) {
        String[] strs = new String[midRes.size()];
        int i = 0;
        for (String s : midRes) {
            strs[i++] = s;
        }
        return getAns(strs);
    }

    private String getAns(String[] strings) {
        int l = 0;
        int r = strings.length - 1;
        return getAns(strings, l, r);
    }

    private String getAns(String[] strings, int l, int r) {
        if (l > r) return "";
        if (l == r) return strings[l];
        int mid = l + ((r - l) >> 1);
        String left = getAns(strings, l, mid);
        String right = getAns(strings, mid + 1, r);
        return merger(left, right);
    }

    private String merger(String left, String right) {
        if (left.equals("")) return right;
        if (right.equals("")) return left;
        int l = left.length() - 1;
        int r = right.length() - 1;
        StringBuilder s = new StringBuilder();
        int carry = 0;
        while (l >= 0 && r >= 0) {
            int sum = left.charAt(l) - '0' + (right.charAt(r) - '0') + carry;
            carry = sum / 10;
            s.append(sum % 10);
            l--;
            r--;
        }
        while (l >= 0) {
            int sum = left.charAt(l) - '0' + carry;
            carry = sum / 10;
            s.append(sum % 10);
            l--;
        }
        while (r >= 0) {
            int sum = right.charAt(r) - '0' + carry;
            carry = sum / 10;
            s.append(sum % 10);
            r--;
        }
        return s.reverse().toString();
    }

    private List<String> helper(String num1, String num2) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < num1.length(); i++) {
            int c1 = num1.charAt(i) - '0';
            if (c1 != 0) {
                int carry = 0;
                StringBuilder s = new StringBuilder();
                for (int k = i + 1; k < num1.length(); k++) {
                    s.append("0");
                }
                for (int j = 0; j < num2.length(); j++) {
                    int sum = (num2.charAt(j) - '0') * c1 + carry;
                    carry = sum / 10;
                    s.append(sum % 10 + "");
                }
                if (carry != 0) {
                    s.append(carry + "");
                }
                res.add(s.reverse().toString());
            }
        }
        return res;
    }
}
